/*
 * Process Hacker -
 *   PE viewer
 *
 * Copyright (C) 2020 dmex
 *
 * This file is part of Process Hacker.
 *
 * Process Hacker is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Process Hacker is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Process Hacker.  If not, see <http://www.gnu.org/licenses/>.
 */

 //
 // This file was ported to the Windows Native API (dmex)
 //

 /* ssdeep
  * Copyright (C) 2002 Andrew Tridgell <tridge@samba.org>
  * Copyright (C) 2006 ManTech International Corporation
  * Copyright (C) 2013 Helmut Grohne <helmut@subdivi.de>
  * Copyright (C) 2017 Tsukasa OI <floss_ssdeep@irq.a4lg.com>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation; either version 2 of the License, or
  * (at your option) any later version.
  *
  * This program is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with this program; if not, write to the Free Software
  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  *
  * Earlier versions of this code were named fuzzy.c and can be found at:
  *     http://www.samba.org/ftp/unpacked/junkcode/spamsum/
  *     http://ssdeep.sf.net/
  */

#include <peview.h>
#include "fuzzy.h"

#if defined(__GNUC__) && __GNUC__ >= 3
#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)
#else
#define likely(x) x
#define unlikely(x) x
#endif

#define ROLLING_WINDOW 7
#define MIN_BLOCKSIZE 3
#define HASH_INIT 0x27
#define NUM_BLOCKHASHES 31

  // Enable bit-parallel string processing only if bit-parallel algorithms
  // are enabled and considered to be efficient.
#if !defined(SSDEEP_DISABLE_POSITION_ARRAY) || !SSDEEP_DISABLE_POSITION_ARRAY
#if SPAMSUM_LENGTH <= 64 && CHAR_MIN >= -256 && CHAR_MAX <= 256 && (CHAR_MAX - CHAR_MIN + 1) <= 256
#define SSDEEP_ENABLE_POSITION_ARRAY
#endif
#endif

typedef struct roll_state
{
    unsigned char window[ROLLING_WINDOW];
    uint32_t h1, h2, h3;
    uint32_t n;
} roll_state, *roll_state_ptr;

static void roll_init(/*@out@*/ roll_state_ptr self)
{
    memset(self, 0, sizeof(roll_state));
}

/*
 * a rolling hash, based on the Adler checksum. By using a rolling hash
 * we can perform auto resynchronisation after inserts/deletes

 * internally, h1 is the sum of the bytes in the window and h2
 * is the sum of the bytes times the index

 * h3 is a shift/xor based rolling hash, and is mostly needed to ensure that
 * we can cope with large blocksize values
 */
static void roll_hash(roll_state_ptr self, unsigned char c)
{
    self->h2 -= self->h1;
    self->h2 += ROLLING_WINDOW * (uint32_t)c;

    self->h1 += (uint32_t)c;
    self->h1 -= (uint32_t)self->window[self->n];

    self->window[self->n] = c;
    self->n++;
    if (self->n == ROLLING_WINDOW)
        self->n = 0;

    /* The original spamsum AND'ed this value with 0xFFFFFFFF which
     * in theory should have no effect. This AND has been removed
     * for performance (jk) */
    self->h3 <<= 5;
    self->h3 ^= c;
}

static uint32_t roll_sum(roll_state_ptr self)
{
    return self->h1 + self->h2 + self->h3;
}

/* A simple non-rolling hash, based on the FNV hash. */
extern const unsigned char sum_table[64][64];

static unsigned char sum_hash(unsigned char c, unsigned char h)
{
    return sum_table[h][c & 0x3f];
}

/* A blockhash contains a signature state for a specific (implicit) blocksize.
 * The blocksize is given by SSDEEP_BS(index). The h and halfh members are the
 * partial FNV hashes, where halfh stops to be reset after digest is
 * SPAMSUM_LENGTH/2 long. The halfh hash is needed be able to truncate digest
 * for the second output hash to stay compatible with ssdeep output. */
typedef struct blockhash_context
{
    unsigned int dindex;
    char digest[SPAMSUM_LENGTH];
    char halfdigest;
    unsigned char h, halfh;
} blockhash_context, *blockhash_context_ptr;

typedef struct fuzzy_state
{
    uint_least64_t total_size;
    uint_least64_t fixed_size;
    uint_least64_t reduce_border;
    unsigned int bhstart, bhend, bhendlimit;
    unsigned int flags;
    uint32_t rollmask;
    struct blockhash_context bh[NUM_BLOCKHASHES];
    roll_state roll;
    unsigned char lasth;
} fuzzy_state, *fuzzy_state_ptr;

#define FUZZY_STATE_NEED_LASTHASH  1u
#define FUZZY_STATE_SIZE_FIXED     2u

#define SSDEEP_BS(index) (((uint32_t)MIN_BLOCKSIZE) << (index))
#define SSDEEP_TOTAL_SIZE_MAX \
  ((uint_least64_t)SSDEEP_BS(NUM_BLOCKHASHES-1) * SPAMSUM_LENGTH)

fuzzy_state_ptr fuzzy_new(void)
{
    fuzzy_state_ptr self;

    if (!(self = PhAllocateSafe(sizeof(fuzzy_state))))
        return NULL;

    self->bhstart = 0;
    self->bhend = 1;
    self->bhendlimit = NUM_BLOCKHASHES - 1;
    self->bh[0].h = HASH_INIT;
    self->bh[0].halfh = HASH_INIT;
    self->bh[0].digest[0] = '\0';
    self->bh[0].halfdigest = '\0';
    self->bh[0].dindex = 0;
    self->total_size = 0;
    self->reduce_border = (uint_least64_t)MIN_BLOCKSIZE * SPAMSUM_LENGTH;
    self->flags = 0;
    self->rollmask = 0;
    roll_init(&self->roll);

    return self;
}

fuzzy_state_ptr fuzzy_clone(fuzzy_state_ptr state)
{
    fuzzy_state_ptr newstate;

    if (!(newstate = PhAllocateSafe(sizeof(fuzzy_state))))
        return NULL;

    memcpy(newstate, state, sizeof(fuzzy_state));
    return newstate;
}

#ifdef S_SPLINT_S
extern const int EOVERFLOW;
#endif

int fuzzy_set_total_input_length(fuzzy_state_ptr state, uint_least64_t total_fixed_length)
{
    unsigned int bi = 0;
    if (total_fixed_length > SSDEEP_TOTAL_SIZE_MAX)
    {
        errno = EOVERFLOW;
        return -1;
    }
    if ((state->flags & FUZZY_STATE_SIZE_FIXED) &&
        state->fixed_size != total_fixed_length)
    {
        errno = EINVAL;
        return -1;
    }
    state->flags |= FUZZY_STATE_SIZE_FIXED;
    state->fixed_size = total_fixed_length;
    while ((uint_least64_t)SSDEEP_BS(bi) * SPAMSUM_LENGTH < total_fixed_length)
    {
        ++bi;
        if (bi == NUM_BLOCKHASHES - 2)
            break;
    }
    ++bi;
    state->bhendlimit = bi;
    return 0;
}


static void fuzzy_try_fork_blockhash(fuzzy_state_ptr self)
{
    blockhash_context_ptr obh, nbh;
    assert(self->bhend > 0);
    obh = self->bh + (self->bhend - 1);
    if (self->bhend <= self->bhendlimit)
    {
        nbh = obh + 1;
        nbh->h = obh->h;
        nbh->halfh = obh->halfh;
        nbh->digest[0] = '\0';
        nbh->halfdigest = '\0';
        nbh->dindex = 0;
        ++self->bhend;
    }
    else if (self->bhend == NUM_BLOCKHASHES &&
        !(self->flags & FUZZY_STATE_NEED_LASTHASH))
    {
        self->flags |= FUZZY_STATE_NEED_LASTHASH;
        self->lasth = obh->h;
    }
}

static void fuzzy_try_reduce_blockhash(fuzzy_state_ptr self)
{
    assert(self->bhstart < self->bhend);
    if (self->bhend - self->bhstart < 2)
        /* Need at least two working hashes. */
        return;
    if (self->reduce_border >= ((self->flags & FUZZY_STATE_SIZE_FIXED) ? self->fixed_size : self->total_size))
        /* Initial blocksize estimate would select this or a smaller
         * blocksize. */
        return;
    if (self->bh[self->bhstart + 1].dindex < SPAMSUM_LENGTH / 2)
        /* Estimate adjustment would select this blocksize. */
        return;
    /* At this point we are clearly no longer interested in the
     * start_blocksize. Get rid of it. */
    ++self->bhstart;
    self->reduce_border *= 2;
    self->rollmask = self->rollmask * 2 + 1;
}

static const char* b64 =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

static void fuzzy_engine_step(fuzzy_state_ptr self, unsigned char c)
{
    uint32_t horg, h;
    unsigned int i;
    /* At each character we update the rolling hash and the normal hashes.
     * When the rolling hash hits a reset value then we emit a normal hash
     * as a element of the signature and reset the normal hash. */
    roll_hash(&self->roll, c);
    horg = roll_sum(&self->roll) + 1;
    h = horg / (uint32_t)MIN_BLOCKSIZE;

    for (i = self->bhstart; i < self->bhend; ++i)
    {
        self->bh[i].h = sum_hash(c, self->bh[i].h);
        self->bh[i].halfh = sum_hash(c, self->bh[i].halfh);
    }
    if (self->flags & FUZZY_STATE_NEED_LASTHASH)
        self->lasth = sum_hash(c, self->lasth);

    /* 0xffffffff !== -1 (mod 3) */
    if (!horg)
        return;
    /* With growing blocksize almost no runs fail the next test. */
    if (likely(h & self->rollmask))
        return;
    /* Delay computation of modulo as possible. */
    if (horg % (uint32_t)MIN_BLOCKSIZE)
        return;
    h >>= self->bhstart;

    i = self->bhstart;
    do
    {
        /* We have hit a reset point. We now emit hashes which are
         * based on all characters in the piece of the message between
         * the last reset point and this one */
        if (unlikely(0 == self->bh[i].dindex)) {
            /* Can only happen 30 times. */
            /* First step for this blocksize. Clone next. */
            fuzzy_try_fork_blockhash(self);
        }

        self->bh[i].digest[self->bh[i].dindex] = b64[self->bh[i].h];
        self->bh[i].halfdigest = b64[self->bh[i].halfh];

        if (self->bh[i].dindex < SPAMSUM_LENGTH - 1) {
            /* We can have a problem with the tail overflowing. The
             * easiest way to cope with this is to only reset the
             * normal hash if we have room for more characters in
             * our signature. This has the effect of combining the
             * last few pieces of the message into a single piece
             * */
            self->bh[i].digest[++(self->bh[i].dindex)] = '\0';
            self->bh[i].h = HASH_INIT;
            if (self->bh[i].dindex < SPAMSUM_LENGTH / 2) {
                self->bh[i].halfh = HASH_INIT;
                self->bh[i].halfdigest = '\0';
            }
        }
        else
            fuzzy_try_reduce_blockhash(self);
        if (h & 1)
            break;
        h >>= 1;
    } while (++i < self->bhend);
}

int fuzzy_update(
    fuzzy_state_ptr self,
    const unsigned char* buffer,
    size_t buffer_size)
{
    if (unlikely(buffer_size > SSDEEP_TOTAL_SIZE_MAX ||
        SSDEEP_TOTAL_SIZE_MAX - buffer_size < self->total_size)) {
        self->total_size = SSDEEP_TOTAL_SIZE_MAX + 1;
    }
    else
        self->total_size += buffer_size;
    for (; buffer_size > 0; ++buffer, --buffer_size)
        fuzzy_engine_step(self, *buffer);
    return 0;
}

static int memcpy_eliminate_sequences(
    char* dst,
    const char* src,
    int n)
{
    const char* srcend = src + n;
    assert(n >= 0);
    if (src < srcend) *dst++ = *src++;
    if (src < srcend) *dst++ = *src++;
    if (src < srcend) *dst++ = *src++;
    while (src < srcend)
    {
        if (*src == dst[-1] && *src == dst[-2] && *src == dst[-3])
        {
            ++src;
            --n;
        }
        else
            *dst++ = *src++;
    }
    return n;
}

int fuzzy_digest(
    fuzzy_state_ptr self,
    /*@out@*/ char* result,
    unsigned int flags)
{
    unsigned int bi = self->bhstart;
    uint32_t h = roll_sum(&self->roll);
    int i, remain = FUZZY_MAX_RESULT - 1; /* Exclude terminating '\0'. */
    /* Verify that our elimination was not overeager. */
    assert(bi == 0 || (uint_least64_t)SSDEEP_BS(bi) / 2 * SPAMSUM_LENGTH <
        self->total_size);

    if (self->total_size > SSDEEP_TOTAL_SIZE_MAX) {
        /* The input exceeds data types. */
        errno = EOVERFLOW;
        return -1;
    }
    /* Fixed size optimization. */
    if ((self->flags & FUZZY_STATE_SIZE_FIXED) &&
        self->fixed_size != self->total_size) {
        errno = EINVAL;
        return -1;
    }
    /* Initial blocksize guess. */
    while ((uint_least64_t)SSDEEP_BS(bi) * SPAMSUM_LENGTH < self->total_size)
        ++bi;
    /* Adapt blocksize guess to actual digest length. */
    if (bi >= self->bhend)
        bi = self->bhend - 1;
    while (bi > self->bhstart && self->bh[bi].dindex < SPAMSUM_LENGTH / 2)
        --bi;
    assert(!(bi > 0 && self->bh[bi].dindex < SPAMSUM_LENGTH / 2));

    i = snprintf(result, (size_t)remain, "%lu:", (unsigned long)SSDEEP_BS(bi));
    if (i <= 0)
        /* Maybe snprintf has set errno here? */
        return -1;
    assert(i < remain);
    remain -= i;
    result += i;
    i = (int)self->bh[bi].dindex;
    assert(i <= remain);
    if ((flags & FUZZY_FLAG_ELIMSEQ) != 0)
        i = memcpy_eliminate_sequences(result, self->bh[bi].digest, i);
    else
        memcpy(result, self->bh[bi].digest, (size_t)i);
    result += i;
    remain -= i;
    if (h != 0)
    {
        assert(remain > 0);
        *result = b64[self->bh[bi].h];
        if ((flags & FUZZY_FLAG_ELIMSEQ) == 0 || i < 3 ||
            *result != result[-1] ||
            *result != result[-2] ||
            *result != result[-3]) {
            ++result;
            --remain;
        }
    }
    else if (self->bh[bi].digest[self->bh[bi].dindex] != '\0') {
        assert(remain > 0);
        *result = self->bh[bi].digest[self->bh[bi].dindex];
        if ((flags & FUZZY_FLAG_ELIMSEQ) == 0 || i < 3 ||
            *result != result[-1] ||
            *result != result[-2] ||
            *result != result[-3]) {
            ++result;
            --remain;
        }
    }
    assert(remain > 0);
    *result++ = ':';
    --remain;
    if (bi < self->bhend - 1)
    {
        ++bi;
        i = (int)self->bh[bi].dindex;
        if ((flags & FUZZY_FLAG_NOTRUNC) == 0 &&
            i > SPAMSUM_LENGTH / 2 - 1)
            i = SPAMSUM_LENGTH / 2 - 1;
        assert(i <= remain);
        if ((flags & FUZZY_FLAG_ELIMSEQ) != 0)
            i = memcpy_eliminate_sequences(result,
                self->bh[bi].digest, i);
        else
            memcpy(result, self->bh[bi].digest, (size_t)i);
        result += i;
        remain -= i;
        if (h != 0) {
            assert(remain > 0);
            h = (flags & FUZZY_FLAG_NOTRUNC) != 0 ? self->bh[bi].h :
                self->bh[bi].halfh;
            *result = b64[h];
            if ((flags & FUZZY_FLAG_ELIMSEQ) == 0 || i < 3 ||
                *result != result[-1] ||
                *result != result[-2] ||
                *result != result[-3])
            {
                ++result;
                --remain;
            }
        }
        else {
            i = (flags & FUZZY_FLAG_NOTRUNC) != 0 ?
                self->bh[bi].digest[self->bh[bi].dindex] : self->bh[bi].halfdigest;
            if (i != '\0') {
                assert(remain > 0);
                *result = i;
                if ((flags & FUZZY_FLAG_ELIMSEQ) == 0 || i < 3 ||
                    *result != result[-1] ||
                    *result != result[-2] ||
                    *result != result[-3])
                {
                    ++result;
                    --remain;
                }
            }
        }
    }
    else if (h != 0)
    {
        assert(bi == 0 || bi == NUM_BLOCKHASHES - 1);
        assert(remain > 0);
        if (bi == 0)
            *result++ = b64[self->bh[bi].h];
        else
            *result++ = b64[self->lasth];
        /* No need to bother with FUZZY_FLAG_ELIMSEQ, because this
         * digest has length 1. */
        --remain;
    }
    *result = '\0';
    return 0;
}

void fuzzy_free(fuzzy_state_ptr self)
{
    PhFree(self);
}

BOOLEAN fuzzy_hash_buffer(
    _In_ PBYTE Buffer,
    _In_ ULONGLONG BufferLength,
    _Out_ PPH_STRING* HashResult
    )
{
    BOOLEAN status = FALSE;
    fuzzy_state_ptr ctx;
    CHAR result[FUZZY_MAX_RESULT];

    if (!(ctx = fuzzy_new()))
        return FALSE;

    if (fuzzy_set_total_input_length(ctx, (uint_least64_t)BufferLength) < 0)
        goto out;

    if (fuzzy_update(ctx, Buffer, (size_t)BufferLength) < 0)
        goto out;

    if (fuzzy_digest(ctx, result, 0) < 0)
        goto out;

    status = TRUE;

    if (HashResult)
    {
        *HashResult = PhZeroExtendToUtf16(result);
    }

out:
    fuzzy_free(ctx);
    return status;
}

static NTSTATUS fuzzy_update_stream(
    _In_ fuzzy_state_ptr state,
    _In_ HANDLE FileHandle,
    _In_ PLARGE_INTEGER FileSize
    )
{
    NTSTATUS status = STATUS_UNSUCCESSFUL;
    IO_STATUS_BLOCK isb;
    ULONGLONG bytesRemaining;
    BYTE buffer[PAGE_SIZE];

    bytesRemaining = FileSize->QuadPart;

    while (bytesRemaining)
    {
        status = NtReadFile(
            FileHandle,
            NULL,
            NULL,
            NULL,
            &isb,
            buffer,
            sizeof(buffer),
            NULL,
            NULL
            );

        if (!NT_SUCCESS(status))
            break;

        if (fuzzy_update(state, buffer, (size_t)isb.Information) < 0)
        {
            status = STATUS_UNSUCCESSFUL;
            break;
        }

        bytesRemaining -= isb.Information;
    }

    if (status == STATUS_END_OF_FILE)
        status = STATUS_SUCCESS;

    return status;
}

int fuzzy_hash_stream(
    _In_ HANDLE FileHandle,
    _In_ PLARGE_INTEGER FileSize,
    _Out_ PSTR result)
{
    fuzzy_state_ptr ctx;
    int ret = -1;

    if (!(ctx = fuzzy_new()))
        return -1;

    if (fuzzy_update_stream(ctx, FileHandle, FileSize) < 0)
        goto out;

    if (fuzzy_digest(ctx, result, 0) < 0)
        goto out;

    ret = 0;
out:
    fuzzy_free(ctx);
    return ret;
}

NTSTATUS fuzzy_hash_file(
    _In_ HANDLE FileHandle,
    _Out_ PPH_STRING* HashResult
    )
{
    NTSTATUS status;
    LARGE_INTEGER fileSize;
    fuzzy_state_ptr ctx;
    CHAR result[FUZZY_MAX_RESULT];

    status = PhGetFileSize(FileHandle, &fileSize);

    if (!NT_SUCCESS(status))
        return status;

    if (!(ctx = fuzzy_new()))
    {
        status = STATUS_UNSUCCESSFUL;
        goto CleanupExit;
    }

    if (fuzzy_set_total_input_length(ctx, (uint_least64_t)fileSize.QuadPart) < 0)
    {
        status = STATUS_UNSUCCESSFUL;
        goto CleanupExit;
    }

    if (fuzzy_update_stream(ctx, FileHandle, &fileSize) < 0)
    {
        status = STATUS_UNSUCCESSFUL;
        goto CleanupExit;
    }

    if (fuzzy_digest(ctx, result, 0) < 0)
    {
        status = STATUS_UNSUCCESSFUL;
        goto CleanupExit;
    }

CleanupExit:
    fuzzy_free(ctx);

    if (NT_SUCCESS(status))
    {
        *HashResult = PhZeroExtendToUtf16(result);
    }

    return status;
}

NTSTATUS fuzzy_hash_filename(
    _In_ PWSTR FileName,
    _Out_ PPH_STRING* HashResult
    )
{
    NTSTATUS status;
    HANDLE fileHandle;
    LARGE_INTEGER fileSize;
    CHAR result[FUZZY_MAX_RESULT];

    status = PhCreateFileWin32(
        &fileHandle,
        FileName,
        FILE_GENERIC_READ,
        FILE_ATTRIBUTE_NORMAL,
        FILE_SHARE_READ | FILE_SHARE_WRITE,
        FILE_OPEN,
        FILE_NON_DIRECTORY_FILE | FILE_SYNCHRONOUS_IO_NONALERT | FILE_SEQUENTIAL_ONLY
        );

    if (NT_SUCCESS(status))
    {
        status = PhGetFileSize(fileHandle, &fileSize);

        if (NT_SUCCESS(status))
        {
            if (fuzzy_hash_stream(fileHandle, &fileSize, result) < 0)
            {
                status = STATUS_UNSUCCESSFUL;
            }
        }

        NtClose(fileHandle);
    }

    if (NT_SUCCESS(status))
    {
        *HashResult = PhZeroExtendToUtf16(result);
    }

    return status;
}

//
// We only accept a match if we have at least one common substring in
// the signature of length ROLLING_WINDOW. This dramatically drops the
// false positive rate for low score thresholds while having
// negligable affect on the rate of spam detection.
//
// return 1 if the two strings do have a common substring, 0 otherwise
//
#ifndef SSDEEP_ENABLE_POSITION_ARRAY
static int has_common_substring(const char* s1, size_t s1len, const char* s2, size_t s2len)
{
    size_t i, j;
    uint32_t hashes[SPAMSUM_LENGTH - (ROLLING_WINDOW - 1)];

    if (s1len < ROLLING_WINDOW)
        return 0;
    if (s2len < ROLLING_WINDOW)
        return 0;

    // there are many possible algorithms for common substring
    // detection. In this case I am re-using the rolling hash code
    // to act as a filter for possible substring matches

    memset(hashes, 0, sizeof(hashes));

    // first compute the windowed rolling hash at each offset in
    // the first string
    struct roll_state state;
    roll_init(&state);

    for (i = 0; i < ROLLING_WINDOW - 1; i++)
        roll_hash(&state, (unsigned char)s1[i]);
    for (i = ROLLING_WINDOW - 1; i < s1len; i++)
    {
        roll_hash(&state, (unsigned char)s1[i]);
        hashes[i - (ROLLING_WINDOW - 1)] = roll_sum(&state);
    }
    s1len -= (ROLLING_WINDOW - 1);

    roll_init(&state);

    // now for each offset in the second string compute the
    // rolling hash and compare it to all of the rolling hashes
    // for the first string. If one matches then we have a
    // candidate substring match. We then confirm that match with
    // a direct string comparison */
    for (j = 0; j < ROLLING_WINDOW - 1; j++)
        roll_hash(&state, (unsigned char)s2[j]);
    for (j = 0; j < s2len - (ROLLING_WINDOW - 1); j++)
    {
        roll_hash(&state, (unsigned char)s2[j + (ROLLING_WINDOW - 1)]);
        uint32_t h = roll_sum(&state);
        for (i = 0; i < s1len; i++)
        {
            // confirm the match after checking potential match
            if (hashes[i] == h && !memcmp(s1 + i, s2 + j, ROLLING_WINDOW))
                return 1;
        }
    }

    return 0;
}
#endif


#ifdef SSDEEP_ENABLE_POSITION_ARRAY

// position array-based version of has_common_substring
static int has_common_substring_pa(const unsigned long long* parray, const char* s2, size_t s2len)
{
    unsigned long long D;
    // ROLLING_WINDOW <= s2len <= 64
    size_t r = ROLLING_WINDOW - 1;
    size_t l;
    const char* ch;
    while (r < s2len)
    {
        // because we want to reuse position array for s1,
        // both s1 and s2 (in the original pseudocode) are reversed.
        l = r - (ROLLING_WINDOW - 1);
        ch = &s2[s2len - 1 - r];
        D = parray[*ch - CHAR_MIN];
        while (D)
        {
            r--;
            D = (D << 1) & parray[*++ch - CHAR_MIN];
            if (r == l && D)
                return 1;
        }
        // Boyer-Moore-like skipping
        r += ROLLING_WINDOW;
    }
    return 0;
}

// position array-based version of edit_distn
static int edit_distn_pa(const unsigned long long* parray, size_t s1len, const char* s2, size_t s2len)
{
    unsigned long long pv, nv, ph, nh, zd, mt, x, y;
    unsigned long long msb;
    size_t i;
    // 0 < s1len <= 64
    int cur = (int)s1len;
    msb = 1ull << (s1len - 1);
    pv = -1;
    nv = 0;
    for (i = 0; i < s2len; i++)
    {
        mt = parray[s2[i] - CHAR_MIN];
        zd = (((mt & pv) + pv) ^ pv) | mt | nv;
        nh = pv & zd;
        if (nh & msb)
            --cur;
        x = nv | ~(pv | zd) | (pv & ~mt & 1ull);
        y = (pv - nh) >> 1;
        ph = (x + y) ^ y;
        if (ph & msb)
            ++cur;
        x = (ph << 1) | 1ull;
        nv = x & zd;
        pv = (nh << 1) | ~(x | zd) | (x & (pv - nh));
    }
    return cur;
}

#endif



// eliminate sequences of longer than 3 identical characters. These
// sequences contain very little information so they tend to just bias
// the result unfairly
static int copy_eliminate_sequences(char** out, size_t outsize, char** in, char etoken)
{
    size_t seq = 0;
    char prev = **in, curr;
    if (!prev || prev == etoken)
        return 1;
    if (!outsize--)
        return 0;
    *(*out)++ = prev;
    ++(*in);
    while (1)
    {
        curr = **in;
        if (!curr || curr == etoken)
            return 1;
        ++(*in);
        if (curr == prev)
        {
            if (++seq >= 3)
            {
                seq = 3;
                continue;
            }
            if (!outsize--)
                return 0;
            *(*out)++ = curr;
        }
        else
        {
            if (!outsize--)
                return 0;
            *(*out)++ = curr;
            seq = 0;
            prev = curr;
        }
    }
    // unreachable
    return 0;
}

//
// this is the low level string scoring algorithm. It takes two strings
// and scores them on a scale of 0-100 where 0 is a terrible match and
// 100 is a great match. The block_size is used to cope with very small
// messages.
//
static uint32_t score_strings(
    const char* s1,
    size_t      s1len,
    const char* s2,
    size_t      s2len,
    unsigned long block_size)
{
    uint32_t score;

#ifdef SSDEEP_ENABLE_POSITION_ARRAY
    unsigned long long parray[CHAR_MAX - CHAR_MIN + 1];
    size_t i;
    // skip short strings
    if (s1len < ROLLING_WINDOW)
        return 0;
    if (s2len < ROLLING_WINDOW)
        return 0;
    // construct position array for faster string algorithms
    memset(parray, 0, sizeof(parray));
    for (i = 0; i < s1len; i++)
        parray[s1[i] - CHAR_MIN] |= 1ull << i;
    // the two strings must have a common substring of length
    // ROLLING_WINDOW to be candidates
    if (!has_common_substring_pa(parray, s2, s2len))
        return 0;
    // compute the edit distance between the two strings. The edit distance gives
    // us a pretty good idea of how closely related the two strings are
    score = edit_distn_pa(parray, s1len, s2, s2len);
#else
    // the two strings must have a common substring of length
    // ROLLING_WINDOW to be candidates
    if (!has_common_substring(s1, s1len, s2, s2len))
        return 0;
    // compute the edit distance between the two strings. The edit distance gives
    // us a pretty good idea of how closely related the two strings are
    score = edit_distn(s1, s1len, s2, s2len);
#endif

    // scale the edit distance by the lengths of the two
    // strings. This changes the score to be a measure of the
    // proportion of the message that has changed rather than an
    // absolute quantity. It also copes with the variability of
    // the string lengths.
    score = (uint32_t)((score * SPAMSUM_LENGTH) / (s1len + s2len));

    // at this stage the score occurs roughly on a 0-SPAMSUM_LENGTH scale,
    // with 0 being a good match and SPAMSUM_LENGTH being a complete
    // mismatch

    // rescale to a 0-100 scale (friendlier to humans)
    score = (100 * score) / SPAMSUM_LENGTH;

    // now re-scale on a 0-100 scale with 0 being a poor match and
    // 100 being a excellent match.
    score = 100 - score;

    //  printf ("s1len: %"PRIu32"  s2len: %"PRIu32"\n", (uint32_t)s1len, (uint32_t)s2len);

    // when the blocksize is small we don't want to exaggerate the match size
    if (block_size >= (99 + ROLLING_WINDOW) / ROLLING_WINDOW * MIN_BLOCKSIZE)
        return score;
    if (score > block_size / MIN_BLOCKSIZE * __min(s1len, s2len))
    {
        score = (uint32_t)(block_size / MIN_BLOCKSIZE * __min(s1len, s2len));
    }
    return score;
}

//
// Given two spamsum strings return a value indicating the degree
// to which they match.
//
int fuzzy_compare(const char* str1, const char* str2)
{
    unsigned long block_size1, block_size2;
    uint32_t score = 0;
    size_t s1b1len, s1b2len, s2b1len, s2b2len;
    char s1b1[SPAMSUM_LENGTH], s1b2[SPAMSUM_LENGTH];
    char s2b1[SPAMSUM_LENGTH], s2b2[SPAMSUM_LENGTH];
    char* s1p, * s2p, * tmp;

    if (NULL == str1 || NULL == str2)
        return -1;

    // each spamsum is prefixed by its block size

    if (sscanf(str1, "%lu:", &block_size1) != 1 ||
        sscanf(str2, "%lu:", &block_size2) != 1) {
        return -1;
    }

    // if the blocksizes don't match then we are comparing
    // apples to oranges. This isn't an 'error' per se. We could
    // have two valid signatures, but they can't be compared.
    if (block_size1 != block_size2 &&
        (block_size1 > ULONG_MAX / 2 || block_size1 * 2 != block_size2) &&
        (block_size1 % 2 == 1 || block_size1 / 2 != block_size2)) {
        return 0;
    }

    // move past the prefix
    s1p = strchr(str1, ':');
    s2p = strchr(str2, ':');

    if (!s1p || !s2p) {
        // badly formed ...
        return -1;
    }

    // there is very little information content is sequences of
    // the same character like 'LLLLL'. Eliminate any sequences
    // longer than 3 while reading two pieces.
    // This is especially important when combined with the
    // has_common_substring() test at score_strings().

    // read the first digest
    ++s1p;
    tmp = s1b1;
    if (!copy_eliminate_sequences(&tmp, SPAMSUM_LENGTH, &s1p, ':'))
        return -1;
    s1b1len = tmp - s1b1;
    if (!*s1p++) {
        // a signature is malformed - it doesn't have 2 parts
        return -1;
    }
    tmp = s1b2;
    if (!copy_eliminate_sequences(&tmp, SPAMSUM_LENGTH, &s1p, ','))
        return -1;
    s1b2len = tmp - s1b2;

    // read the second digest
    ++s2p;
    tmp = s2b1;
    if (!copy_eliminate_sequences(&tmp, SPAMSUM_LENGTH, &s2p, ':'))
        return -1;
    s2b1len = tmp - s2b1;
    if (!*s2p++) {
        // a signature is malformed - it doesn't have 2 parts
        return -1;
    }
    tmp = s2b2;
    if (!copy_eliminate_sequences(&tmp, SPAMSUM_LENGTH, &s2p, ','))
        return -1;
    s2b2len = tmp - s2b2;

    // Now that we know the strings are both well formed, are they
    // identical? We could save ourselves some work here
    if (block_size1 == block_size2 && s1b1len == s2b1len && s1b2len == s2b2len) {
        if (!memcmp(s1b1, s2b1, s1b1len) && !memcmp(s1b2, s2b2, s1b2len)) {
            return 100;
        }
    }

    // each signature has a string for two block sizes. We now
    // choose how to combine the two block sizes. We checked above
    // that they have at least one block size in common
    if (block_size1 <= ULONG_MAX / 2) {
        if (block_size1 == block_size2) {
            uint32_t score1, score2;
            score1 = score_strings(s1b1, s1b1len, s2b1, s2b1len, block_size1);
            score2 = score_strings(s1b2, s1b2len, s2b2, s2b2len, block_size1 * 2);
            score = __max(score1, score2);
        }
        else if (block_size1 * 2 == block_size2) {
            score = score_strings(s2b1, s2b1len, s1b2, s1b2len, block_size2);
        }
        else {
            score = score_strings(s1b1, s1b1len, s2b2, s2b2len, block_size1);
        }
    }
    else {
        if (block_size1 == block_size2) {
            score = score_strings(s1b1, s1b1len, s2b1, s2b1len, block_size1);
        }
        else if (block_size1 % 2 == 0 && block_size1 / 2 == block_size2) {
            score = score_strings(s1b1, s1b1len, s2b2, s2b2len, block_size1);
        }
        else {
            score = 0;
        }
    }

    return (int)score;
}

// Precomputed patrial FNV hash table
const unsigned char sum_table[64][64] =
{
  { // 0x00
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
  },
  { // 0x01
    0x13, 0x12, 0x11, 0x10, 0x17, 0x16, 0x15, 0x14, 0x1b, 0x1a, 0x19, 0x18, 0x1f, 0x1e, 0x1d, 0x1c,
    0x03, 0x02, 0x01, 0x00, 0x07, 0x06, 0x05, 0x04, 0x0b, 0x0a, 0x09, 0x08, 0x0f, 0x0e, 0x0d, 0x0c,
    0x33, 0x32, 0x31, 0x30, 0x37, 0x36, 0x35, 0x34, 0x3b, 0x3a, 0x39, 0x38, 0x3f, 0x3e, 0x3d, 0x3c,
    0x23, 0x22, 0x21, 0x20, 0x27, 0x26, 0x25, 0x24, 0x2b, 0x2a, 0x29, 0x28, 0x2f, 0x2e, 0x2d, 0x2c,
  },
  { // 0x02
    0x26, 0x27, 0x24, 0x25, 0x22, 0x23, 0x20, 0x21, 0x2e, 0x2f, 0x2c, 0x2d, 0x2a, 0x2b, 0x28, 0x29,
    0x36, 0x37, 0x34, 0x35, 0x32, 0x33, 0x30, 0x31, 0x3e, 0x3f, 0x3c, 0x3d, 0x3a, 0x3b, 0x38, 0x39,
    0x06, 0x07, 0x04, 0x05, 0x02, 0x03, 0x00, 0x01, 0x0e, 0x0f, 0x0c, 0x0d, 0x0a, 0x0b, 0x08, 0x09,
    0x16, 0x17, 0x14, 0x15, 0x12, 0x13, 0x10, 0x11, 0x1e, 0x1f, 0x1c, 0x1d, 0x1a, 0x1b, 0x18, 0x19,
  },
  { // 0x03
    0x39, 0x38, 0x3b, 0x3a, 0x3d, 0x3c, 0x3f, 0x3e, 0x31, 0x30, 0x33, 0x32, 0x35, 0x34, 0x37, 0x36,
    0x29, 0x28, 0x2b, 0x2a, 0x2d, 0x2c, 0x2f, 0x2e, 0x21, 0x20, 0x23, 0x22, 0x25, 0x24, 0x27, 0x26,
    0x19, 0x18, 0x1b, 0x1a, 0x1d, 0x1c, 0x1f, 0x1e, 0x11, 0x10, 0x13, 0x12, 0x15, 0x14, 0x17, 0x16,
    0x09, 0x08, 0x0b, 0x0a, 0x0d, 0x0c, 0x0f, 0x0e, 0x01, 0x00, 0x03, 0x02, 0x05, 0x04, 0x07, 0x06,
  },
  { // 0x04
    0x0c, 0x0d, 0x0e, 0x0f, 0x08, 0x09, 0x0a, 0x0b, 0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03,
    0x1c, 0x1d, 0x1e, 0x1f, 0x18, 0x19, 0x1a, 0x1b, 0x14, 0x15, 0x16, 0x17, 0x10, 0x11, 0x12, 0x13,
    0x2c, 0x2d, 0x2e, 0x2f, 0x28, 0x29, 0x2a, 0x2b, 0x24, 0x25, 0x26, 0x27, 0x20, 0x21, 0x22, 0x23,
    0x3c, 0x3d, 0x3e, 0x3f, 0x38, 0x39, 0x3a, 0x3b, 0x34, 0x35, 0x36, 0x37, 0x30, 0x31, 0x32, 0x33,
  },
  { // 0x05
    0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10,
    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
    0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30,
    0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28, 0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20,
  },
  { // 0x06
    0x32, 0x33, 0x30, 0x31, 0x36, 0x37, 0x34, 0x35, 0x3a, 0x3b, 0x38, 0x39, 0x3e, 0x3f, 0x3c, 0x3d,
    0x22, 0x23, 0x20, 0x21, 0x26, 0x27, 0x24, 0x25, 0x2a, 0x2b, 0x28, 0x29, 0x2e, 0x2f, 0x2c, 0x2d,
    0x12, 0x13, 0x10, 0x11, 0x16, 0x17, 0x14, 0x15, 0x1a, 0x1b, 0x18, 0x19, 0x1e, 0x1f, 0x1c, 0x1d,
    0x02, 0x03, 0x00, 0x01, 0x06, 0x07, 0x04, 0x05, 0x0a, 0x0b, 0x08, 0x09, 0x0e, 0x0f, 0x0c, 0x0d,
  },
  { // 0x07
    0x05, 0x04, 0x07, 0x06, 0x01, 0x00, 0x03, 0x02, 0x0d, 0x0c, 0x0f, 0x0e, 0x09, 0x08, 0x0b, 0x0a,
    0x15, 0x14, 0x17, 0x16, 0x11, 0x10, 0x13, 0x12, 0x1d, 0x1c, 0x1f, 0x1e, 0x19, 0x18, 0x1b, 0x1a,
    0x25, 0x24, 0x27, 0x26, 0x21, 0x20, 0x23, 0x22, 0x2d, 0x2c, 0x2f, 0x2e, 0x29, 0x28, 0x2b, 0x2a,
    0x35, 0x34, 0x37, 0x36, 0x31, 0x30, 0x33, 0x32, 0x3d, 0x3c, 0x3f, 0x3e, 0x39, 0x38, 0x3b, 0x3a,
  },
  { // 0x08
    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
    0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
  },
  { // 0x09
    0x2b, 0x2a, 0x29, 0x28, 0x2f, 0x2e, 0x2d, 0x2c, 0x23, 0x22, 0x21, 0x20, 0x27, 0x26, 0x25, 0x24,
    0x3b, 0x3a, 0x39, 0x38, 0x3f, 0x3e, 0x3d, 0x3c, 0x33, 0x32, 0x31, 0x30, 0x37, 0x36, 0x35, 0x34,
    0x0b, 0x0a, 0x09, 0x08, 0x0f, 0x0e, 0x0d, 0x0c, 0x03, 0x02, 0x01, 0x00, 0x07, 0x06, 0x05, 0x04,
    0x1b, 0x1a, 0x19, 0x18, 0x1f, 0x1e, 0x1d, 0x1c, 0x13, 0x12, 0x11, 0x10, 0x17, 0x16, 0x15, 0x14,
  },
  { // 0x0a
    0x3e, 0x3f, 0x3c, 0x3d, 0x3a, 0x3b, 0x38, 0x39, 0x36, 0x37, 0x34, 0x35, 0x32, 0x33, 0x30, 0x31,
    0x2e, 0x2f, 0x2c, 0x2d, 0x2a, 0x2b, 0x28, 0x29, 0x26, 0x27, 0x24, 0x25, 0x22, 0x23, 0x20, 0x21,
    0x1e, 0x1f, 0x1c, 0x1d, 0x1a, 0x1b, 0x18, 0x19, 0x16, 0x17, 0x14, 0x15, 0x12, 0x13, 0x10, 0x11,
    0x0e, 0x0f, 0x0c, 0x0d, 0x0a, 0x0b, 0x08, 0x09, 0x06, 0x07, 0x04, 0x05, 0x02, 0x03, 0x00, 0x01,
  },
  { // 0x0b
    0x11, 0x10, 0x13, 0x12, 0x15, 0x14, 0x17, 0x16, 0x19, 0x18, 0x1b, 0x1a, 0x1d, 0x1c, 0x1f, 0x1e,
    0x01, 0x00, 0x03, 0x02, 0x05, 0x04, 0x07, 0x06, 0x09, 0x08, 0x0b, 0x0a, 0x0d, 0x0c, 0x0f, 0x0e,
    0x31, 0x30, 0x33, 0x32, 0x35, 0x34, 0x37, 0x36, 0x39, 0x38, 0x3b, 0x3a, 0x3d, 0x3c, 0x3f, 0x3e,
    0x21, 0x20, 0x23, 0x22, 0x25, 0x24, 0x27, 0x26, 0x29, 0x28, 0x2b, 0x2a, 0x2d, 0x2c, 0x2f, 0x2e,
  },
  { // 0x0c
    0x24, 0x25, 0x26, 0x27, 0x20, 0x21, 0x22, 0x23, 0x2c, 0x2d, 0x2e, 0x2f, 0x28, 0x29, 0x2a, 0x2b,
    0x34, 0x35, 0x36, 0x37, 0x30, 0x31, 0x32, 0x33, 0x3c, 0x3d, 0x3e, 0x3f, 0x38, 0x39, 0x3a, 0x3b,
    0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03, 0x0c, 0x0d, 0x0e, 0x0f, 0x08, 0x09, 0x0a, 0x0b,
    0x14, 0x15, 0x16, 0x17, 0x10, 0x11, 0x12, 0x13, 0x1c, 0x1d, 0x1e, 0x1f, 0x18, 0x19, 0x1a, 0x1b,
  },
  { // 0x0d
    0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30, 0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38,
    0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20, 0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28,
    0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10, 0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18,
    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00, 0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
  },
  { // 0x0e
    0x0a, 0x0b, 0x08, 0x09, 0x0e, 0x0f, 0x0c, 0x0d, 0x02, 0x03, 0x00, 0x01, 0x06, 0x07, 0x04, 0x05,
    0x1a, 0x1b, 0x18, 0x19, 0x1e, 0x1f, 0x1c, 0x1d, 0x12, 0x13, 0x10, 0x11, 0x16, 0x17, 0x14, 0x15,
    0x2a, 0x2b, 0x28, 0x29, 0x2e, 0x2f, 0x2c, 0x2d, 0x22, 0x23, 0x20, 0x21, 0x26, 0x27, 0x24, 0x25,
    0x3a, 0x3b, 0x38, 0x39, 0x3e, 0x3f, 0x3c, 0x3d, 0x32, 0x33, 0x30, 0x31, 0x36, 0x37, 0x34, 0x35,
  },
  { // 0x0f
    0x1d, 0x1c, 0x1f, 0x1e, 0x19, 0x18, 0x1b, 0x1a, 0x15, 0x14, 0x17, 0x16, 0x11, 0x10, 0x13, 0x12,
    0x0d, 0x0c, 0x0f, 0x0e, 0x09, 0x08, 0x0b, 0x0a, 0x05, 0x04, 0x07, 0x06, 0x01, 0x00, 0x03, 0x02,
    0x3d, 0x3c, 0x3f, 0x3e, 0x39, 0x38, 0x3b, 0x3a, 0x35, 0x34, 0x37, 0x36, 0x31, 0x30, 0x33, 0x32,
    0x2d, 0x2c, 0x2f, 0x2e, 0x29, 0x28, 0x2b, 0x2a, 0x25, 0x24, 0x27, 0x26, 0x21, 0x20, 0x23, 0x22,
  },
  { // 0x10
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
  },
  { // 0x11
    0x03, 0x02, 0x01, 0x00, 0x07, 0x06, 0x05, 0x04, 0x0b, 0x0a, 0x09, 0x08, 0x0f, 0x0e, 0x0d, 0x0c,
    0x13, 0x12, 0x11, 0x10, 0x17, 0x16, 0x15, 0x14, 0x1b, 0x1a, 0x19, 0x18, 0x1f, 0x1e, 0x1d, 0x1c,
    0x23, 0x22, 0x21, 0x20, 0x27, 0x26, 0x25, 0x24, 0x2b, 0x2a, 0x29, 0x28, 0x2f, 0x2e, 0x2d, 0x2c,
    0x33, 0x32, 0x31, 0x30, 0x37, 0x36, 0x35, 0x34, 0x3b, 0x3a, 0x39, 0x38, 0x3f, 0x3e, 0x3d, 0x3c,
  },
  { // 0x12
    0x16, 0x17, 0x14, 0x15, 0x12, 0x13, 0x10, 0x11, 0x1e, 0x1f, 0x1c, 0x1d, 0x1a, 0x1b, 0x18, 0x19,
    0x06, 0x07, 0x04, 0x05, 0x02, 0x03, 0x00, 0x01, 0x0e, 0x0f, 0x0c, 0x0d, 0x0a, 0x0b, 0x08, 0x09,
    0x36, 0x37, 0x34, 0x35, 0x32, 0x33, 0x30, 0x31, 0x3e, 0x3f, 0x3c, 0x3d, 0x3a, 0x3b, 0x38, 0x39,
    0x26, 0x27, 0x24, 0x25, 0x22, 0x23, 0x20, 0x21, 0x2e, 0x2f, 0x2c, 0x2d, 0x2a, 0x2b, 0x28, 0x29,
  },
  { // 0x13
    0x29, 0x28, 0x2b, 0x2a, 0x2d, 0x2c, 0x2f, 0x2e, 0x21, 0x20, 0x23, 0x22, 0x25, 0x24, 0x27, 0x26,
    0x39, 0x38, 0x3b, 0x3a, 0x3d, 0x3c, 0x3f, 0x3e, 0x31, 0x30, 0x33, 0x32, 0x35, 0x34, 0x37, 0x36,
    0x09, 0x08, 0x0b, 0x0a, 0x0d, 0x0c, 0x0f, 0x0e, 0x01, 0x00, 0x03, 0x02, 0x05, 0x04, 0x07, 0x06,
    0x19, 0x18, 0x1b, 0x1a, 0x1d, 0x1c, 0x1f, 0x1e, 0x11, 0x10, 0x13, 0x12, 0x15, 0x14, 0x17, 0x16,
  },
  { // 0x14
    0x3c, 0x3d, 0x3e, 0x3f, 0x38, 0x39, 0x3a, 0x3b, 0x34, 0x35, 0x36, 0x37, 0x30, 0x31, 0x32, 0x33,
    0x2c, 0x2d, 0x2e, 0x2f, 0x28, 0x29, 0x2a, 0x2b, 0x24, 0x25, 0x26, 0x27, 0x20, 0x21, 0x22, 0x23,
    0x1c, 0x1d, 0x1e, 0x1f, 0x18, 0x19, 0x1a, 0x1b, 0x14, 0x15, 0x16, 0x17, 0x10, 0x11, 0x12, 0x13,
    0x0c, 0x0d, 0x0e, 0x0f, 0x08, 0x09, 0x0a, 0x0b, 0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03,
  },
  { // 0x15
    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
    0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10,
    0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28, 0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20,
    0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30,
  },
  { // 0x16
    0x22, 0x23, 0x20, 0x21, 0x26, 0x27, 0x24, 0x25, 0x2a, 0x2b, 0x28, 0x29, 0x2e, 0x2f, 0x2c, 0x2d,
    0x32, 0x33, 0x30, 0x31, 0x36, 0x37, 0x34, 0x35, 0x3a, 0x3b, 0x38, 0x39, 0x3e, 0x3f, 0x3c, 0x3d,
    0x02, 0x03, 0x00, 0x01, 0x06, 0x07, 0x04, 0x05, 0x0a, 0x0b, 0x08, 0x09, 0x0e, 0x0f, 0x0c, 0x0d,
    0x12, 0x13, 0x10, 0x11, 0x16, 0x17, 0x14, 0x15, 0x1a, 0x1b, 0x18, 0x19, 0x1e, 0x1f, 0x1c, 0x1d,
  },
  { // 0x17
    0x35, 0x34, 0x37, 0x36, 0x31, 0x30, 0x33, 0x32, 0x3d, 0x3c, 0x3f, 0x3e, 0x39, 0x38, 0x3b, 0x3a,
    0x25, 0x24, 0x27, 0x26, 0x21, 0x20, 0x23, 0x22, 0x2d, 0x2c, 0x2f, 0x2e, 0x29, 0x28, 0x2b, 0x2a,
    0x15, 0x14, 0x17, 0x16, 0x11, 0x10, 0x13, 0x12, 0x1d, 0x1c, 0x1f, 0x1e, 0x19, 0x18, 0x1b, 0x1a,
    0x05, 0x04, 0x07, 0x06, 0x01, 0x00, 0x03, 0x02, 0x0d, 0x0c, 0x0f, 0x0e, 0x09, 0x08, 0x0b, 0x0a,
  },
  { // 0x18
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
    0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  },
  { // 0x19
    0x1b, 0x1a, 0x19, 0x18, 0x1f, 0x1e, 0x1d, 0x1c, 0x13, 0x12, 0x11, 0x10, 0x17, 0x16, 0x15, 0x14,
    0x0b, 0x0a, 0x09, 0x08, 0x0f, 0x0e, 0x0d, 0x0c, 0x03, 0x02, 0x01, 0x00, 0x07, 0x06, 0x05, 0x04,
    0x3b, 0x3a, 0x39, 0x38, 0x3f, 0x3e, 0x3d, 0x3c, 0x33, 0x32, 0x31, 0x30, 0x37, 0x36, 0x35, 0x34,
    0x2b, 0x2a, 0x29, 0x28, 0x2f, 0x2e, 0x2d, 0x2c, 0x23, 0x22, 0x21, 0x20, 0x27, 0x26, 0x25, 0x24,
  },
  { // 0x1a
    0x2e, 0x2f, 0x2c, 0x2d, 0x2a, 0x2b, 0x28, 0x29, 0x26, 0x27, 0x24, 0x25, 0x22, 0x23, 0x20, 0x21,
    0x3e, 0x3f, 0x3c, 0x3d, 0x3a, 0x3b, 0x38, 0x39, 0x36, 0x37, 0x34, 0x35, 0x32, 0x33, 0x30, 0x31,
    0x0e, 0x0f, 0x0c, 0x0d, 0x0a, 0x0b, 0x08, 0x09, 0x06, 0x07, 0x04, 0x05, 0x02, 0x03, 0x00, 0x01,
    0x1e, 0x1f, 0x1c, 0x1d, 0x1a, 0x1b, 0x18, 0x19, 0x16, 0x17, 0x14, 0x15, 0x12, 0x13, 0x10, 0x11,
  },
  { // 0x1b
    0x01, 0x00, 0x03, 0x02, 0x05, 0x04, 0x07, 0x06, 0x09, 0x08, 0x0b, 0x0a, 0x0d, 0x0c, 0x0f, 0x0e,
    0x11, 0x10, 0x13, 0x12, 0x15, 0x14, 0x17, 0x16, 0x19, 0x18, 0x1b, 0x1a, 0x1d, 0x1c, 0x1f, 0x1e,
    0x21, 0x20, 0x23, 0x22, 0x25, 0x24, 0x27, 0x26, 0x29, 0x28, 0x2b, 0x2a, 0x2d, 0x2c, 0x2f, 0x2e,
    0x31, 0x30, 0x33, 0x32, 0x35, 0x34, 0x37, 0x36, 0x39, 0x38, 0x3b, 0x3a, 0x3d, 0x3c, 0x3f, 0x3e,
  },
  { // 0x1c
    0x14, 0x15, 0x16, 0x17, 0x10, 0x11, 0x12, 0x13, 0x1c, 0x1d, 0x1e, 0x1f, 0x18, 0x19, 0x1a, 0x1b,
    0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03, 0x0c, 0x0d, 0x0e, 0x0f, 0x08, 0x09, 0x0a, 0x0b,
    0x34, 0x35, 0x36, 0x37, 0x30, 0x31, 0x32, 0x33, 0x3c, 0x3d, 0x3e, 0x3f, 0x38, 0x39, 0x3a, 0x3b,
    0x24, 0x25, 0x26, 0x27, 0x20, 0x21, 0x22, 0x23, 0x2c, 0x2d, 0x2e, 0x2f, 0x28, 0x29, 0x2a, 0x2b,
  },
  { // 0x1d
    0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20, 0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28,
    0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30, 0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38,
    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00, 0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
    0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10, 0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18,
  },
  { // 0x1e
    0x3a, 0x3b, 0x38, 0x39, 0x3e, 0x3f, 0x3c, 0x3d, 0x32, 0x33, 0x30, 0x31, 0x36, 0x37, 0x34, 0x35,
    0x2a, 0x2b, 0x28, 0x29, 0x2e, 0x2f, 0x2c, 0x2d, 0x22, 0x23, 0x20, 0x21, 0x26, 0x27, 0x24, 0x25,
    0x1a, 0x1b, 0x18, 0x19, 0x1e, 0x1f, 0x1c, 0x1d, 0x12, 0x13, 0x10, 0x11, 0x16, 0x17, 0x14, 0x15,
    0x0a, 0x0b, 0x08, 0x09, 0x0e, 0x0f, 0x0c, 0x0d, 0x02, 0x03, 0x00, 0x01, 0x06, 0x07, 0x04, 0x05,
  },
  { // 0x1f
    0x0d, 0x0c, 0x0f, 0x0e, 0x09, 0x08, 0x0b, 0x0a, 0x05, 0x04, 0x07, 0x06, 0x01, 0x00, 0x03, 0x02,
    0x1d, 0x1c, 0x1f, 0x1e, 0x19, 0x18, 0x1b, 0x1a, 0x15, 0x14, 0x17, 0x16, 0x11, 0x10, 0x13, 0x12,
    0x2d, 0x2c, 0x2f, 0x2e, 0x29, 0x28, 0x2b, 0x2a, 0x25, 0x24, 0x27, 0x26, 0x21, 0x20, 0x23, 0x22,
    0x3d, 0x3c, 0x3f, 0x3e, 0x39, 0x38, 0x3b, 0x3a, 0x35, 0x34, 0x37, 0x36, 0x31, 0x30, 0x33, 0x32,
  },
  { // 0x20
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
  },
  { // 0x21
    0x33, 0x32, 0x31, 0x30, 0x37, 0x36, 0x35, 0x34, 0x3b, 0x3a, 0x39, 0x38, 0x3f, 0x3e, 0x3d, 0x3c,
    0x23, 0x22, 0x21, 0x20, 0x27, 0x26, 0x25, 0x24, 0x2b, 0x2a, 0x29, 0x28, 0x2f, 0x2e, 0x2d, 0x2c,
    0x13, 0x12, 0x11, 0x10, 0x17, 0x16, 0x15, 0x14, 0x1b, 0x1a, 0x19, 0x18, 0x1f, 0x1e, 0x1d, 0x1c,
    0x03, 0x02, 0x01, 0x00, 0x07, 0x06, 0x05, 0x04, 0x0b, 0x0a, 0x09, 0x08, 0x0f, 0x0e, 0x0d, 0x0c,
  },
  { // 0x22
    0x06, 0x07, 0x04, 0x05, 0x02, 0x03, 0x00, 0x01, 0x0e, 0x0f, 0x0c, 0x0d, 0x0a, 0x0b, 0x08, 0x09,
    0x16, 0x17, 0x14, 0x15, 0x12, 0x13, 0x10, 0x11, 0x1e, 0x1f, 0x1c, 0x1d, 0x1a, 0x1b, 0x18, 0x19,
    0x26, 0x27, 0x24, 0x25, 0x22, 0x23, 0x20, 0x21, 0x2e, 0x2f, 0x2c, 0x2d, 0x2a, 0x2b, 0x28, 0x29,
    0x36, 0x37, 0x34, 0x35, 0x32, 0x33, 0x30, 0x31, 0x3e, 0x3f, 0x3c, 0x3d, 0x3a, 0x3b, 0x38, 0x39,
  },
  { // 0x23
    0x19, 0x18, 0x1b, 0x1a, 0x1d, 0x1c, 0x1f, 0x1e, 0x11, 0x10, 0x13, 0x12, 0x15, 0x14, 0x17, 0x16,
    0x09, 0x08, 0x0b, 0x0a, 0x0d, 0x0c, 0x0f, 0x0e, 0x01, 0x00, 0x03, 0x02, 0x05, 0x04, 0x07, 0x06,
    0x39, 0x38, 0x3b, 0x3a, 0x3d, 0x3c, 0x3f, 0x3e, 0x31, 0x30, 0x33, 0x32, 0x35, 0x34, 0x37, 0x36,
    0x29, 0x28, 0x2b, 0x2a, 0x2d, 0x2c, 0x2f, 0x2e, 0x21, 0x20, 0x23, 0x22, 0x25, 0x24, 0x27, 0x26,
  },
  { // 0x24
    0x2c, 0x2d, 0x2e, 0x2f, 0x28, 0x29, 0x2a, 0x2b, 0x24, 0x25, 0x26, 0x27, 0x20, 0x21, 0x22, 0x23,
    0x3c, 0x3d, 0x3e, 0x3f, 0x38, 0x39, 0x3a, 0x3b, 0x34, 0x35, 0x36, 0x37, 0x30, 0x31, 0x32, 0x33,
    0x0c, 0x0d, 0x0e, 0x0f, 0x08, 0x09, 0x0a, 0x0b, 0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03,
    0x1c, 0x1d, 0x1e, 0x1f, 0x18, 0x19, 0x1a, 0x1b, 0x14, 0x15, 0x16, 0x17, 0x10, 0x11, 0x12, 0x13,
  },
  { // 0x25
    0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30,
    0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28, 0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20,
    0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10,
    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
  },
  { // 0x26
    0x12, 0x13, 0x10, 0x11, 0x16, 0x17, 0x14, 0x15, 0x1a, 0x1b, 0x18, 0x19, 0x1e, 0x1f, 0x1c, 0x1d,
    0x02, 0x03, 0x00, 0x01, 0x06, 0x07, 0x04, 0x05, 0x0a, 0x0b, 0x08, 0x09, 0x0e, 0x0f, 0x0c, 0x0d,
    0x32, 0x33, 0x30, 0x31, 0x36, 0x37, 0x34, 0x35, 0x3a, 0x3b, 0x38, 0x39, 0x3e, 0x3f, 0x3c, 0x3d,
    0x22, 0x23, 0x20, 0x21, 0x26, 0x27, 0x24, 0x25, 0x2a, 0x2b, 0x28, 0x29, 0x2e, 0x2f, 0x2c, 0x2d,
  },
  { // 0x27
    0x25, 0x24, 0x27, 0x26, 0x21, 0x20, 0x23, 0x22, 0x2d, 0x2c, 0x2f, 0x2e, 0x29, 0x28, 0x2b, 0x2a,
    0x35, 0x34, 0x37, 0x36, 0x31, 0x30, 0x33, 0x32, 0x3d, 0x3c, 0x3f, 0x3e, 0x39, 0x38, 0x3b, 0x3a,
    0x05, 0x04, 0x07, 0x06, 0x01, 0x00, 0x03, 0x02, 0x0d, 0x0c, 0x0f, 0x0e, 0x09, 0x08, 0x0b, 0x0a,
    0x15, 0x14, 0x17, 0x16, 0x11, 0x10, 0x13, 0x12, 0x1d, 0x1c, 0x1f, 0x1e, 0x19, 0x18, 0x1b, 0x1a,
  },
  { // 0x28
    0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
    0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
  },
  { // 0x29
    0x0b, 0x0a, 0x09, 0x08, 0x0f, 0x0e, 0x0d, 0x0c, 0x03, 0x02, 0x01, 0x00, 0x07, 0x06, 0x05, 0x04,
    0x1b, 0x1a, 0x19, 0x18, 0x1f, 0x1e, 0x1d, 0x1c, 0x13, 0x12, 0x11, 0x10, 0x17, 0x16, 0x15, 0x14,
    0x2b, 0x2a, 0x29, 0x28, 0x2f, 0x2e, 0x2d, 0x2c, 0x23, 0x22, 0x21, 0x20, 0x27, 0x26, 0x25, 0x24,
    0x3b, 0x3a, 0x39, 0x38, 0x3f, 0x3e, 0x3d, 0x3c, 0x33, 0x32, 0x31, 0x30, 0x37, 0x36, 0x35, 0x34,
  },
  { // 0x2a
    0x1e, 0x1f, 0x1c, 0x1d, 0x1a, 0x1b, 0x18, 0x19, 0x16, 0x17, 0x14, 0x15, 0x12, 0x13, 0x10, 0x11,
    0x0e, 0x0f, 0x0c, 0x0d, 0x0a, 0x0b, 0x08, 0x09, 0x06, 0x07, 0x04, 0x05, 0x02, 0x03, 0x00, 0x01,
    0x3e, 0x3f, 0x3c, 0x3d, 0x3a, 0x3b, 0x38, 0x39, 0x36, 0x37, 0x34, 0x35, 0x32, 0x33, 0x30, 0x31,
    0x2e, 0x2f, 0x2c, 0x2d, 0x2a, 0x2b, 0x28, 0x29, 0x26, 0x27, 0x24, 0x25, 0x22, 0x23, 0x20, 0x21,
  },
  { // 0x2b
    0x31, 0x30, 0x33, 0x32, 0x35, 0x34, 0x37, 0x36, 0x39, 0x38, 0x3b, 0x3a, 0x3d, 0x3c, 0x3f, 0x3e,
    0x21, 0x20, 0x23, 0x22, 0x25, 0x24, 0x27, 0x26, 0x29, 0x28, 0x2b, 0x2a, 0x2d, 0x2c, 0x2f, 0x2e,
    0x11, 0x10, 0x13, 0x12, 0x15, 0x14, 0x17, 0x16, 0x19, 0x18, 0x1b, 0x1a, 0x1d, 0x1c, 0x1f, 0x1e,
    0x01, 0x00, 0x03, 0x02, 0x05, 0x04, 0x07, 0x06, 0x09, 0x08, 0x0b, 0x0a, 0x0d, 0x0c, 0x0f, 0x0e,
  },
  { // 0x2c
    0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03, 0x0c, 0x0d, 0x0e, 0x0f, 0x08, 0x09, 0x0a, 0x0b,
    0x14, 0x15, 0x16, 0x17, 0x10, 0x11, 0x12, 0x13, 0x1c, 0x1d, 0x1e, 0x1f, 0x18, 0x19, 0x1a, 0x1b,
    0x24, 0x25, 0x26, 0x27, 0x20, 0x21, 0x22, 0x23, 0x2c, 0x2d, 0x2e, 0x2f, 0x28, 0x29, 0x2a, 0x2b,
    0x34, 0x35, 0x36, 0x37, 0x30, 0x31, 0x32, 0x33, 0x3c, 0x3d, 0x3e, 0x3f, 0x38, 0x39, 0x3a, 0x3b,
  },
  { // 0x2d
    0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10, 0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18,
    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00, 0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
    0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30, 0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38,
    0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20, 0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28,
  },
  { // 0x2e
    0x2a, 0x2b, 0x28, 0x29, 0x2e, 0x2f, 0x2c, 0x2d, 0x22, 0x23, 0x20, 0x21, 0x26, 0x27, 0x24, 0x25,
    0x3a, 0x3b, 0x38, 0x39, 0x3e, 0x3f, 0x3c, 0x3d, 0x32, 0x33, 0x30, 0x31, 0x36, 0x37, 0x34, 0x35,
    0x0a, 0x0b, 0x08, 0x09, 0x0e, 0x0f, 0x0c, 0x0d, 0x02, 0x03, 0x00, 0x01, 0x06, 0x07, 0x04, 0x05,
    0x1a, 0x1b, 0x18, 0x19, 0x1e, 0x1f, 0x1c, 0x1d, 0x12, 0x13, 0x10, 0x11, 0x16, 0x17, 0x14, 0x15,
  },
  { // 0x2f
    0x3d, 0x3c, 0x3f, 0x3e, 0x39, 0x38, 0x3b, 0x3a, 0x35, 0x34, 0x37, 0x36, 0x31, 0x30, 0x33, 0x32,
    0x2d, 0x2c, 0x2f, 0x2e, 0x29, 0x28, 0x2b, 0x2a, 0x25, 0x24, 0x27, 0x26, 0x21, 0x20, 0x23, 0x22,
    0x1d, 0x1c, 0x1f, 0x1e, 0x19, 0x18, 0x1b, 0x1a, 0x15, 0x14, 0x17, 0x16, 0x11, 0x10, 0x13, 0x12,
    0x0d, 0x0c, 0x0f, 0x0e, 0x09, 0x08, 0x0b, 0x0a, 0x05, 0x04, 0x07, 0x06, 0x01, 0x00, 0x03, 0x02,
  },
  { // 0x30
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
  },
  { // 0x31
    0x23, 0x22, 0x21, 0x20, 0x27, 0x26, 0x25, 0x24, 0x2b, 0x2a, 0x29, 0x28, 0x2f, 0x2e, 0x2d, 0x2c,
    0x33, 0x32, 0x31, 0x30, 0x37, 0x36, 0x35, 0x34, 0x3b, 0x3a, 0x39, 0x38, 0x3f, 0x3e, 0x3d, 0x3c,
    0x03, 0x02, 0x01, 0x00, 0x07, 0x06, 0x05, 0x04, 0x0b, 0x0a, 0x09, 0x08, 0x0f, 0x0e, 0x0d, 0x0c,
    0x13, 0x12, 0x11, 0x10, 0x17, 0x16, 0x15, 0x14, 0x1b, 0x1a, 0x19, 0x18, 0x1f, 0x1e, 0x1d, 0x1c,
  },
  { // 0x32
    0x36, 0x37, 0x34, 0x35, 0x32, 0x33, 0x30, 0x31, 0x3e, 0x3f, 0x3c, 0x3d, 0x3a, 0x3b, 0x38, 0x39,
    0x26, 0x27, 0x24, 0x25, 0x22, 0x23, 0x20, 0x21, 0x2e, 0x2f, 0x2c, 0x2d, 0x2a, 0x2b, 0x28, 0x29,
    0x16, 0x17, 0x14, 0x15, 0x12, 0x13, 0x10, 0x11, 0x1e, 0x1f, 0x1c, 0x1d, 0x1a, 0x1b, 0x18, 0x19,
    0x06, 0x07, 0x04, 0x05, 0x02, 0x03, 0x00, 0x01, 0x0e, 0x0f, 0x0c, 0x0d, 0x0a, 0x0b, 0x08, 0x09,
  },
  { // 0x33
    0x09, 0x08, 0x0b, 0x0a, 0x0d, 0x0c, 0x0f, 0x0e, 0x01, 0x00, 0x03, 0x02, 0x05, 0x04, 0x07, 0x06,
    0x19, 0x18, 0x1b, 0x1a, 0x1d, 0x1c, 0x1f, 0x1e, 0x11, 0x10, 0x13, 0x12, 0x15, 0x14, 0x17, 0x16,
    0x29, 0x28, 0x2b, 0x2a, 0x2d, 0x2c, 0x2f, 0x2e, 0x21, 0x20, 0x23, 0x22, 0x25, 0x24, 0x27, 0x26,
    0x39, 0x38, 0x3b, 0x3a, 0x3d, 0x3c, 0x3f, 0x3e, 0x31, 0x30, 0x33, 0x32, 0x35, 0x34, 0x37, 0x36,
  },
  { // 0x34
    0x1c, 0x1d, 0x1e, 0x1f, 0x18, 0x19, 0x1a, 0x1b, 0x14, 0x15, 0x16, 0x17, 0x10, 0x11, 0x12, 0x13,
    0x0c, 0x0d, 0x0e, 0x0f, 0x08, 0x09, 0x0a, 0x0b, 0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03,
    0x3c, 0x3d, 0x3e, 0x3f, 0x38, 0x39, 0x3a, 0x3b, 0x34, 0x35, 0x36, 0x37, 0x30, 0x31, 0x32, 0x33,
    0x2c, 0x2d, 0x2e, 0x2f, 0x28, 0x29, 0x2a, 0x2b, 0x24, 0x25, 0x26, 0x27, 0x20, 0x21, 0x22, 0x23,
  },
  { // 0x35
    0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28, 0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20,
    0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30,
    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
    0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10,
  },
  { // 0x36
    0x02, 0x03, 0x00, 0x01, 0x06, 0x07, 0x04, 0x05, 0x0a, 0x0b, 0x08, 0x09, 0x0e, 0x0f, 0x0c, 0x0d,
    0x12, 0x13, 0x10, 0x11, 0x16, 0x17, 0x14, 0x15, 0x1a, 0x1b, 0x18, 0x19, 0x1e, 0x1f, 0x1c, 0x1d,
    0x22, 0x23, 0x20, 0x21, 0x26, 0x27, 0x24, 0x25, 0x2a, 0x2b, 0x28, 0x29, 0x2e, 0x2f, 0x2c, 0x2d,
    0x32, 0x33, 0x30, 0x31, 0x36, 0x37, 0x34, 0x35, 0x3a, 0x3b, 0x38, 0x39, 0x3e, 0x3f, 0x3c, 0x3d,
  },
  { // 0x37
    0x15, 0x14, 0x17, 0x16, 0x11, 0x10, 0x13, 0x12, 0x1d, 0x1c, 0x1f, 0x1e, 0x19, 0x18, 0x1b, 0x1a,
    0x05, 0x04, 0x07, 0x06, 0x01, 0x00, 0x03, 0x02, 0x0d, 0x0c, 0x0f, 0x0e, 0x09, 0x08, 0x0b, 0x0a,
    0x35, 0x34, 0x37, 0x36, 0x31, 0x30, 0x33, 0x32, 0x3d, 0x3c, 0x3f, 0x3e, 0x39, 0x38, 0x3b, 0x3a,
    0x25, 0x24, 0x27, 0x26, 0x21, 0x20, 0x23, 0x22, 0x2d, 0x2c, 0x2f, 0x2e, 0x29, 0x28, 0x2b, 0x2a,
  },
  { // 0x38
    0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
    0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
  },
  { // 0x39
    0x3b, 0x3a, 0x39, 0x38, 0x3f, 0x3e, 0x3d, 0x3c, 0x33, 0x32, 0x31, 0x30, 0x37, 0x36, 0x35, 0x34,
    0x2b, 0x2a, 0x29, 0x28, 0x2f, 0x2e, 0x2d, 0x2c, 0x23, 0x22, 0x21, 0x20, 0x27, 0x26, 0x25, 0x24,
    0x1b, 0x1a, 0x19, 0x18, 0x1f, 0x1e, 0x1d, 0x1c, 0x13, 0x12, 0x11, 0x10, 0x17, 0x16, 0x15, 0x14,
    0x0b, 0x0a, 0x09, 0x08, 0x0f, 0x0e, 0x0d, 0x0c, 0x03, 0x02, 0x01, 0x00, 0x07, 0x06, 0x05, 0x04,
  },
  { // 0x3a
    0x0e, 0x0f, 0x0c, 0x0d, 0x0a, 0x0b, 0x08, 0x09, 0x06, 0x07, 0x04, 0x05, 0x02, 0x03, 0x00, 0x01,
    0x1e, 0x1f, 0x1c, 0x1d, 0x1a, 0x1b, 0x18, 0x19, 0x16, 0x17, 0x14, 0x15, 0x12, 0x13, 0x10, 0x11,
    0x2e, 0x2f, 0x2c, 0x2d, 0x2a, 0x2b, 0x28, 0x29, 0x26, 0x27, 0x24, 0x25, 0x22, 0x23, 0x20, 0x21,
    0x3e, 0x3f, 0x3c, 0x3d, 0x3a, 0x3b, 0x38, 0x39, 0x36, 0x37, 0x34, 0x35, 0x32, 0x33, 0x30, 0x31,
  },
  { // 0x3b
    0x21, 0x20, 0x23, 0x22, 0x25, 0x24, 0x27, 0x26, 0x29, 0x28, 0x2b, 0x2a, 0x2d, 0x2c, 0x2f, 0x2e,
    0x31, 0x30, 0x33, 0x32, 0x35, 0x34, 0x37, 0x36, 0x39, 0x38, 0x3b, 0x3a, 0x3d, 0x3c, 0x3f, 0x3e,
    0x01, 0x00, 0x03, 0x02, 0x05, 0x04, 0x07, 0x06, 0x09, 0x08, 0x0b, 0x0a, 0x0d, 0x0c, 0x0f, 0x0e,
    0x11, 0x10, 0x13, 0x12, 0x15, 0x14, 0x17, 0x16, 0x19, 0x18, 0x1b, 0x1a, 0x1d, 0x1c, 0x1f, 0x1e,
  },
  { // 0x3c
    0x34, 0x35, 0x36, 0x37, 0x30, 0x31, 0x32, 0x33, 0x3c, 0x3d, 0x3e, 0x3f, 0x38, 0x39, 0x3a, 0x3b,
    0x24, 0x25, 0x26, 0x27, 0x20, 0x21, 0x22, 0x23, 0x2c, 0x2d, 0x2e, 0x2f, 0x28, 0x29, 0x2a, 0x2b,
    0x14, 0x15, 0x16, 0x17, 0x10, 0x11, 0x12, 0x13, 0x1c, 0x1d, 0x1e, 0x1f, 0x18, 0x19, 0x1a, 0x1b,
    0x04, 0x05, 0x06, 0x07, 0x00, 0x01, 0x02, 0x03, 0x0c, 0x0d, 0x0e, 0x0f, 0x08, 0x09, 0x0a, 0x0b,
  },
  { // 0x3d
    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00, 0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
    0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10, 0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18,
    0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20, 0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28,
    0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30, 0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38,
  },
  { // 0x3e
    0x1a, 0x1b, 0x18, 0x19, 0x1e, 0x1f, 0x1c, 0x1d, 0x12, 0x13, 0x10, 0x11, 0x16, 0x17, 0x14, 0x15,
    0x0a, 0x0b, 0x08, 0x09, 0x0e, 0x0f, 0x0c, 0x0d, 0x02, 0x03, 0x00, 0x01, 0x06, 0x07, 0x04, 0x05,
    0x3a, 0x3b, 0x38, 0x39, 0x3e, 0x3f, 0x3c, 0x3d, 0x32, 0x33, 0x30, 0x31, 0x36, 0x37, 0x34, 0x35,
    0x2a, 0x2b, 0x28, 0x29, 0x2e, 0x2f, 0x2c, 0x2d, 0x22, 0x23, 0x20, 0x21, 0x26, 0x27, 0x24, 0x25,
  },
  { // 0x3f
    0x2d, 0x2c, 0x2f, 0x2e, 0x29, 0x28, 0x2b, 0x2a, 0x25, 0x24, 0x27, 0x26, 0x21, 0x20, 0x23, 0x22,
    0x3d, 0x3c, 0x3f, 0x3e, 0x39, 0x38, 0x3b, 0x3a, 0x35, 0x34, 0x37, 0x36, 0x31, 0x30, 0x33, 0x32,
    0x0d, 0x0c, 0x0f, 0x0e, 0x09, 0x08, 0x0b, 0x0a, 0x05, 0x04, 0x07, 0x06, 0x01, 0x00, 0x03, 0x02,
    0x1d, 0x1c, 0x1f, 0x1e, 0x19, 0x18, 0x1b, 0x1a, 0x15, 0x14, 0x17, 0x16, 0x11, 0x10, 0x13, 0x12,
  },
};
